"""
素数查找程序
使用埃拉托斯特尼筛法优化性能
"""

import math
import time

def is_prime_naive(n):
    """
    基础判断素数方法（性能较低，用于对比）
    
    Args:
        n: 要判断的数字
    
    Returns:
        bool: 是否为素数
    """
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    
    # 检查6k±1形式的因子
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

def sieve_of_eratosthenes(limit):
    """
    使用埃拉托斯特尼筛法找出所有素数（性能优化）
    
    Args:
        limit: 查找上限
    
    Returns:
        list: 素数列表
    """
    if limit < 2:
        return []
    
    # 初始化标记数组
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    
    # 筛法过程：标记非素数
    for i in range(2, int(math.sqrt(limit)) + 1):
        if is_prime[i]:
            # 将i的倍数标记为非素数
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
    
    # 收集所有素数
    primes = [i for i in range(2, limit + 1) if is_prime[i]]
    return primes

def print_primes(primes, primes_per_line=5):
    """
    按指定格式打印素数
    
    Args:
        primes: 素数列表
        primes_per_line: 每行显示的素数个数
    """
    print(f"\n1~20000内的素数共有 {len(primes)} 个：")
    print("=" * 60)
    
    for i in range(0, len(primes), primes_per_line):
        line = primes[i:i + primes_per_line]
        print(" ".join(f"{num:6d}" for num in line))

def performance_analysis():
    """
    性能分析和对比
    """
    limit = 20000
    
    print("性能对比分析")
    print("=" * 50)
    
    # 测试筛法性能
    start_time = time.time()
    primes_sieve = sieve_of_eratosthenes(limit)
    sieve_time = time.time() - start_time
    
    # 测试基础方法性能（抽样测试）
    sample_size = min(1000, limit)
    start_time = time.time()
    primes_naive_sample = [i for i in range(2, sample_size + 1) if is_prime_naive(i)]
    naive_time = time.time() - start_time
    
    # 估算完整基础方法的时间
    estimated_naive_time = naive_time * (limit / sample_size)
    
    print(f"筛法执行时间: {sieve_time:.4f} 秒")
    print(f"基础方法估算时间: {estimated_naive_time:.2f} 秒")
    print(f"性能提升倍数: {estimated_naive_time/sieve_time:.1f} 倍")
    
    return primes_sieve
